package alogrithm;

import java.util.HashMap;
import java.util.HashSet;

public class Demo1 {

    //剑指24 反转链表
    public ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode(-1);
        ListNode temp = head;

        while (true) {
            if (temp.next == null) {
                ListNode be = dummy.next;
                dummy.next = temp;
                temp.next = be;
                break;
            }
            ListNode mid = temp.next;
            ListNode behind = dummy.next;
            dummy.next = temp;
            dummy.next.next = behind;
            temp = mid;

        }

        return dummy.next;
    }


    //剑指35  复杂链表的复制
    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        Node cur = head;
        HashMap<Node, Node> map = new HashMap<>();

        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;

        }
        return map.get(head);
    }

    public static void main(String[] args) {
       /* Node node1 = new Node(1);
        Node node2 = new Node(2);

        node1.next = node2;
        node1.random = node2;
        node2.next = null;
        node2.random = node2;
        Demo1 demo1 = new Demo1();
        demo1.copyRandomList(node1);*/

        Demo1 demo1 = new Demo1();
        System.out.println(demo1.search(new int[]{1, 3}, 1));

    }


    //剑指 05.替换空格   "We are happy."
    public String replaceSpace(String s) {
        StringBuffer buffer = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 32) {
                buffer.append("%20");
                continue;
            }
            buffer.append(s.charAt(i));

        }
        return buffer.toString();

    }

    //剑指58 左旋字符串
    public String reverseLeftWords(String s, int n) {
        if (n == 0) return s;
        return s.substring(n, s.length()) + s.substring(0, n);
    }

    //剑指03 数组中重复的数字
    public int findRepeatNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.add(nums[i])) return nums[i];
        }
        return -1;
    }


    //剑指53 在排序数组中查找数字
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return 0;
        int ans = 0;
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + right >>> 1;
            if (nums[mid] == target) {
                ans++;
                //向左遍历
                int l = mid - 1;
                while (l >= 0 && nums[l] == target) {
                    ans++;
                    l--;
                }
                ;
                //向右遍历
                int r = mid + 1;
                while (r < nums.length && nums[r] == target) {
                    ans++;
                    r++;
                }
                ;
                return ans;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;

    }


    //剑53 0~n-1中缺失的数字
    public int missingNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) return nums[i] - 1;
        }
        return -1;
    }

    //剑指04 二维数组中的查找
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null) return false;
        int rows = matrix.length, columns = matrix[0].length;
        for (int i = rows - 1; i >= 0; i--) {
            if (matrix[i][columns - 1] < target) return false;
            if (matrix[i][0] > target) continue;
            int left = 0, right = columns - 1;
            while (left <= right) {
                int mid = left + right >>> 1;
                if (matrix[i][mid] == target) return true;
                else if (matrix[i][mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;

                }

            }


        }

        return false;
    }

    //剑指11 旋转数组的最小数字
    public int minArray(int[] numbers) {
        if (numbers.length < 2) return numbers[0];
        for (int i = 0; i < numbers.length; i++) {
            if (i + 1 < numbers.length && numbers[i] > numbers[i + 1]) return numbers[i + 1];
        }
        return numbers[0];
    }

    //

}
